The present invention generally relates to an image processing method and apparatus and particularly to a method and apparatus for creating an outline of a figure to be painted out from outline vectors which represent the contour of the figure, and then painting the figure by painting an internal region surrounded by the outline through a scanning operation.
Conventionally, a seed filling method or a scan filling method is known as a method of painting out an arbitrary region of a figure. Although the seed filling method is adopted in many image processors, it has a defect that the processing speed is slower as compared with the scan filling method.
In the scan filling method, the contour of a figure to be painted out is represented by outline vectors, as shown in FIG. 1, which are so oriented that the figure is painted out by painting out the left side of the outline vectors. For example, from the initial data shown in FIG. 2A, the outline vectors shown in FIG. 2B are created. Such an outline as shown in FIG. 3A is created from these outline vectors, and in the scanning operation in the x direction, i.e., horizontal direction, the painting-out operation is started at an odd-numbered intersection between each horizontal scanning line and the outline, with the painting-out operation being stopped at an even-numbered intersection, thus resulting in such a figure as shown in FIG. 3B.
An image processing apparatus adopting a scan filling method as described above to paint a figure is disclosed in Japanese Patent Publication (Tokkosho) No. 53-41017. The image processing apparatus creates an outline from outline vectors by means of an algorithm of the known Bresenham method, and as a result, outlines as shown in FIG. 4A, FIG. 5A, and FIG. 6A, for example, are provided. Each outline is composed of outline components.
In the scanning operation along each of the horizontal scanning lines in the x direction, the printing-out operation is started at an odd-numbered intersection between each horizontal scanning line and the outline, with a pixel on the odd-numbered intersection included in the painting-out region. The painting-out operation is stopped at an even-numbered intersection, with a pixel on the even-numbered intersection being included in the painting-out region.
In the case of creating an outline by the conventional image processing apparatus described above, when outline vectors overlap each other on the same pixel as at the top portion in FIG. 4A or at the central portion in FIG. 5A, the pixel becomes a component of the outline, or a point on the outline. Accordingly, when the horizontal scanning line intersects that outline component, all pixels on the right side thereof, inclusive of the outline component, are painted out, so that the painting out errors as shown in FIG. 4B and FIG. 5B are caused. On the other hand, when an outline is created along a horizontal scanning line as shown in FIG. 6A, if the last component of the outline falls on an odd-numbered pixel counted from the initial pixel that the scanning line intersects, the pixel on the right side of the odd-numbered pixel is painted out, thus causing such painting-out errors as shown in FIG. 6B.
In order to prevent such error from being caused, according to the conventional processing operation, the position of a pixel deviated by one dot in the x-axial direction from the outline component on the top portion is also plotted as an outline component, as shown in, for example, FIG. 3A. Also, for the outline parallel to the scanning direction, the processing operation is effected so that the outline may be even-numbered dots in length or only a starting point and an end point are plotted. In this case, however, the processing speed of a host computer effecting the processing operation becomes slower, with the load on the host computer becoming larger. Furthermore, when the outline obtained through the processing operation effected on the vector font is stored in a mask ROM, etc., and scaled down or rotated, such painting out errors may be caused again. For example, when the outline shown in FIG. 7A is contracted as shown in FIG. 7B, painting-out errors as above-described will happen. When the processing is effected on the outline shown in FIG. 8A, the outline becomes such as shown in FIG. 8B. When it is painted out, a figure as shown in FIG. 8C, which is different in shape from the figure shown in FIG. 8A, is obtained.
Outlines which will cause errors and/or change shapes of original figures in such a painting-out operation are shown, as typical examples, in FIGS. 9A, 9B, 9C, and 9D. The outlines shown in FIG.9A and 9B are similar to those shown in FIG. 4A and FIG. 6A. FIG. 9C shows a case wherein a pixel is shared by two boundaries, and FIG. 9D shows a case wherein two boundaries are in complete conformity with each other as the most extreme case of FIG.9C. The outline components surrounded by a circle mark are those which cause the error.
In the above-described conventional image processing apparatus, because such outlines as shown in FIGS. 9A through 9D are produced during the outline creation, it is necessary to process the outline in order to prevent the errors from being caused during the figure painting-out operation, resulting in a problem that the processing speed becomes slower. Furthermore, because of the above-described outline processing, the shape of a figure after the painting-out becomes considerably different from its original shape, resulting in a problem that the characteristics of the vector font with easy magnification and rotation and beautiful font can not be fully utilized.
FIG. 18 is a drawing showing another example of the outline vectors, and FIG. 19 is a drawing showing an outline created by the conventional method using the Bresenham algorithm on the vector C in FIG. 18, and FIGS. 22A and 22B are flow charts showing the conventional method using the Bresenham algorithm.
Hereinbelow, with reference to the flow charts in FIGS. 22A and 22B, the procedure of creating the outline of FIG. 19 from the vector, C of FIG.18 will be described.
First, at step S71, the absolute value of the abscissa (x) difference between the starting point (xc1, yc1) of vector C and the end point (xc2, yc2) thereof is calculated as "deltax" and the absolute value of the ordinate (y) difference is calculated as "deltay". At step S72, when "deltax" is larger than "deltay", the x-axis is selected as a major axis and flow proceeds to step S73. But when "deltax" is smaller, the y-axis is selected as a major axis and a corresponding procedure is carried out. At step S73, an initial value of "e" and constants (cons1 cons2) are set. This "e" assumes a value cons2-deltax (e=cons2-deltax) when the flow proceeds to step S83. The expression e=cons2-deltax is obtained by multiplying 2*deltax on both sides of the expression e=deltay/deltax-0.5 to make each side an integer and then by newly replacing 2*deltax*e with e. Accordingly, e&gt;0 means that the y-ordinate of the vector at an intersection of the vector and a line running parallel to the y-axis across a prospective pixel indication point is closer to the ordinate of another pixel indication point which is obtained by increasing or decreasing the ordinate of the prospective pixel indication point by one, than to the ordinate of the prospective indication point. Next, the flow proceeds from step S74 to step S78 or step S79, and whether an increment (inc=1) or a decrement (inc=-1) is to be made is determined in accordance with the sense and inclination of the vector. At step S80, the starting point of the vector is made the first display point of the pixel. Next, at step S81, the discrimination is made as to whether e&gt;0 or not, and when e is not larger than 0, after calculating e=e+cons2 at step S83, a pixel on a predetermined display point is displayed at step S84, while in the case of a positive e, increment or decrement of the y ordinate is carried out at step S82 and at the same time e is calculated to be e=e+cons1 and thereafter, at step S84, a pixel is displayed on a next display point where the y ordinate is increased (or decreased) by one from the predetermined display point. Then, after increasing or decreasing the abscissa (x) by one at step S85, the flow is returned from step S86 to step S81, and thereafter, the same procedure is repeated up to the end point of the vector.
By the above-described processing the outline shown in FIG. 19 is created from the vector C shown in FIG. 18.
However, even when painting is made based on this outline by the odd-even method shown in FIG. 17, the scanning is stopped at the pixels indicated by white circles, and the inside of the outline can not be painted out. In order to solve this problem, a conventional method uses a 3-by-3 mesh filter in the following manner. The outline is scanned in the x direction by the filter, and during the scanning, the central portion of the filter is arranged so as to fall on each pixel shown in FIG.19. When a matrix pattern obtained through the scanning by the filter becomes the same as any of the patterns as shown in FIG. 20, the pixel in the center of the matrix pattern obtained is painted, and when it becomes different from those patterns shown in FIG. 20, the central pixel thereof is not painted. In this way, unnecessary pixels are removed.
For example, when the filter is applied to the leftmost pixel in FIG. 19, a matrix pattern obtained becomes the same as the pattern at the left end of the lower row in FIG. 20, and thus the pixel is painted. Since none of the patterns shown in FIG. 20 is obtained with respect to the pixel on the right side of the leftmost pixel, it is not painted. In this way, pixels marked with a circle having an x mark contained therein are painted, with pixels indicated only by circle marks being excluded from painting. The patterns shown in FIG. 20 are used for a vector tending to the direction in which y ordinates decrease, like the vector C, and the patterns as shown in FIG. 21 are used for a vector tending to the direction in which y ordinates increase. In the case where the y-axis is used as the major axis, it is not necessary to use the filter because the outline as shown in FIG. 20 is not obtained in such a case.
As described above, according to the conventional image processing method, in the case where the x-axis is the major axis, the processing with the 3-by-3 mesh filter is required after the processing using the Bresenham algorithm, thus resulting in a problem of taking time in processing.